3531. Счастливый день?

Кот Мурчик очень любит охотится. Это увлечение для него есть настолько важным, что он считает, что день для него является счастливым, если для него удачно пройдёт охота в этот день. Охотится он каждый день и обычно на мышей.

Выходя на охоту, Мурчик знает, что всего есть n мышек. Кроме того, опытный кот знает для каждой мыши вероятность того, что он её поймает. Мурчик считает, что день для него является счастливым, если он поймает не менее k мышей.

Так как с математикой у него, как и у его друга Мурзика, возникают большие проблемы, то он просит вас помочь ему вычислить вероятность того, что день для него окажется счастливым.

Вход. В первой строке задано два целых числа n (0 < n < 21) – количество мышей, на которых Мурчик будет охотится, и k (0 ≤ k ≤ n) – минимальное количество мышей, которое нужно поймать Мурчику, чтобы он считал для себе день счастливым.

В последующих n строках задано n вещественных чисел p[i] – вероятность того, что Мурчик поймает i-ую мышку.

Выход. Выведите единственное число – вероятность того, что день окажется для Мурчика счастливым. Выводить число необходимо с 8-ю знаками после десятичной точки.

Пример входа	Пример выхода
3 2 0.5 0.5 0.5	0.500000000

РЕШЕНИЕ

комбинаторика – генерация подмножеств

Анализ алгоритма

Переберем все подмножества мышей и найдем вероятность того, что Мурчик их поймает. Просуммируем вероятности поймать лишь те подмножества мышей, которые содержат в себе как минимум k грызунов.

Реализация алгоритма

Вероятности поймать Мурчику мышек занесем в массив p.

#define MAX 21

double p[MAX];

Читаем входные данные.

scanf("%d %d",&n,&k);

for(res = i = 0; i < n; i++) scanf("%lf",&p[i]);

Перебираем все подмножества мышек – от пустого до максимального.

for(i = 0; i < (1 << n); i++)

{

В переменной val вычисляем вероятность поймать подмножество мышек, задаваемое маской i. В переменной cnt подсчитываем количество мышек в подмножестве.

for(val = 1, cnt = j = 0; j < n; j++)

if (i & (1 << j))

{

cnt++;

val = val * p[j];

}

else val = val * (1 - p[j]);

Если подмножество, которое задается маской i, содержит хотя бы k мышек, то учитываем вероятность поймать его.

if (cnt >= k) res += val;

}

Выводим искомую вероятность.

printf("%.8lf\n",res);

Java реализация

import java.io.*;

import java.util.*;

public class Main

{

static double p[];

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

con.useLocale(Locale.US);

int n = con.nextInt();

int k = con.nextInt();

int i, j, cnt;

double val, res = 0;

p = new double[n];

for(i = 0; i < n; i++) p[i] = con.nextDouble();

for(i = 0; i < (1 << n); i++)

{

for(val = 1, cnt = 0, j = 0; j < n; j++)

if ((i & (1 << j)) > 0)

{

cnt++;

val = val * p[j];

}

else val = val * (1 - p[j]);

if (cnt >= k) res += val;

}

System.out.println(res);

}

}